21.3 Build Heap


How long does it take to build a heap with N items using repeated
calls to insert?

	O(N log N)


A heap of N items can be built in linear time in the worst case.


Given a complete binary tree with N items in arbitrary order
(OR given an array of N items in arbitrary order),
what must be done to produce a heap with the order property?

	percolate-down each item


Which positions on the tree don't need to be percolated down?

	the leaf nodes in the tree can't move down


Which node in the tree should be percolated down first/last?

	percolate down in reverse level order
	when percolateDown called on node i
	descendants of node i have already been done


Show the result of buildHeap on the array. (use a min-heap)

	8 5 2 7 3 4 6 9 2

	       8
	      / \
	     /   \
	    5     2
	   / \   / \
	  7   3 4   6
	 / \
	9   2


Classwork
You may work with a partner.
Show the result of buildHeap on the array. (use a min-heap)

	7 8 8 4 5 4 3 1 2

	       7
	      / \
	     /   \
	    8     8
	   / \   / \
	  4   5 4   3
	 / \
	1   2


Explain the code for buildHeap.

    private void buildHeap( ) {
        for( int i = currentSize / 2; i > 0; i-- )
            percolateDown( i );
    }


How can you show that buildHeap is O(N)?

	the sum of node-heights is a bound on the percolate steps
	the sum of node-heights is N - H - 1
		for each node, mark one left edge, then right edges
		each edge is marked once, except right side
		tree has N-1 edges, H edges on right side